package com.demo.排序算法.冒泡排序;

import java.util.Arrays;

/**
 * 冒泡排序
 * 核心: 通过相邻的两个元素比较，或大，或小，将最大或最小的元素'冒'到最前面
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{1, 2, 5, 9, 3, 6, 8, 4, 7};
        // 对数组进行从小到大的排序 使用 冒泡排序
        bubbleSort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    // 冒泡排序
    private static void bubbleSort(int[] arrays) {
        // 为 null 或者 数组长度小于 2 不需要排序
        if (arrays == null || arrays.length < 2) {
            return;
        }
        // 使用冒泡排序将最小的元素'冒'到前面
        // 所以需要从后往前相邻比较，若小交换，若大不变
        // 每次排外一趟，即最小的就冒到前面了，所以8趟就可以了 因为最后一趟不用排了
        for(int x = 0; x < arrays.length - 1; x++) {
            // 对每趟进行冒泡 相邻比较
            // 每趟都会排好一个数 所以比较到 y > x 即可
            for(int y = arrays.length - 1; y > x; y--) {
                // 相邻两个元素比较 小就交换，否则不变
                if (arrays[y] < arrays[y - 1]) {
                    swap(arrays, y, y-1);
                }
            }
        }
    }

    // 交换函数
    private static void swap(int[] arrays, int i, int j) {
        if (0 <= i && 0 <= j && i < arrays.length && j < arrays.length && i != j) {
            // 0 和 A 异或 都是 A 本身
            // A 和 A 异或 都是 0
            arrays[i] = arrays[i] ^ arrays[j];
            // arrays[j] = arrays[i] ^ arrays[j] ^ arrays[j];
            arrays[j] = arrays[i] ^ arrays[j];
            // arrays[i] = arrays[i] ^ arrays[j] ^ (arrays[j] = arrays[i]);
            arrays[i] = arrays[i] ^ arrays[j];
        }
    }
}
